The process of sorting data records using a computer usually involves reading a series of unordered data records from an input file on an external storage medium, such as magnetic tape, disk, cards, etc., ordering these data records into the desired sequence and writing the sorted data records to an output file on a second external storage medium. The sorting process generally requires a large share of the resources of a computer system and a significant amount of computer time. The present invention provides a sorting method which requires a smaller share of computer resources and reduced computing time.
Sorting a large number of data records usually requires a two stage process. The first stage is the initial sorting of as many data records as can be accommodated by the computer memory, and creating strings of sorted data records. The second stage involves merging these strings of data records into a final desired sequence of sorted data records.
Known techniques for sorting require the following thirteen steps to perform the two stages sorting process: (1) initializing; (2) reading a portion of the data records from the input file into first computer memory locations, called the data input area; (3) extracting sort keys from the data records and writing copies of the sort keys, along with pointers to each data record, into second computer memory locations, called the key extraction area; (4) sorting the keys in the key extraction area; (5) moving the data records from the data input area to third computer memory locations, called the sort-work output area; (6) writing the data records in sorted sequence as a string to an external storage device; (7) repeating steps 2 through 6 until all data records have been processed; (8) reinitializing; (9) reading a portion of data from each string into fourth computer memory locations, called the merge input area; (10) merging the data records by moving the sequentially foremost data record, called the "winner," into fifth computer memory locations, called the sort output area; (11) writing the sorted data records from the sort output area to an external storage device; (12) repeating steps 10 and 11 until all data records in the merge input area from at least one of the strings are exhausted; and (13) repeating steps 9 through 12 until all data records in all strings have been processed. Steps 1 through 7 constitute the first or initial sort stage; steps 8 through 13 constitute the second or merge stage. Each of these steps will now be described in greater detail.
In step 1, control information describing the data to be sorted, the desired sorting sequence, (ascending or descending), location and characteristics of the keys which determine the ordering of a data record, etc. is obtained. Several sections of internal computer memory are also established. For purposes of this explanation only the areas of computer memory necessary to understand this disclosure will be described. (1) A data input area ("DIA") which contains the records to be sorted. I/O commands to read the data from the input file will place the records into the data input area. (2) The key extraction area which contains copies of the sort keys of individual records. The key extraction area is not an essential element of the invention but will aid the description. (3) The sort-work output area ("SWK") which serves as a collection area for records in sorted order. These sorted records will be written from the sort-work output area to an intermediate external storage device. The sort-work output area consists of one or more sort-work output area buffers. Each buffer is a contiguous area of computer memory generally containing one or more records in sorted order.
Any of these memory areas may be one large contiguous section of memory or several smaller contiguous sections of memory. For description purposes only, these memory areas will be described as though they are one contiguous area. During the initialization step, these three areas (data input area, sort-work output area, key extraction area) are set to an empty state.
In step 2 some unsorted data records are read from the input file by issuing one or more I/O commands to the external storage device containing the input file. The input data records are placed into the data input area in an arbitrary order. At this point in the process, the key extraction area and sort-work output area remain empty.
Step 3 extracts a sort key from each record and places a copy of it in the key extraction area. At this time, it is helpful to associate a pointer (record location or address) to the original record with each sort key in the key extraction area. During the key extraction process, the key may be modified such as by compaction, translation, or expansion, or by adding other useful information to each sort key. Generally the sort key and pointer are much smaller than the data records, so the key extraction area is usually smaller than the data input area.
Step 4 sorts the entries in the key extraction area into the desired order. This may be accomplished by any of the many available sorting techniques (Quicksort, bubble sort, or other sorting techniques). The sort step results in the key extraction area entries being ordered based on the values of the extracted sort keys.
In Step 5, the data records are moved from the data input area to the sort-work output area in sorted order. This is accomplished by using the ordered entries in the key extraction area to determine which record to move from the data input area to the sort-work output area. A series of data records in sorted order, as those now stored in the sort-work output area, is called a string.
Step 6 writes the string from the sort-work output area to the external storage device. This is done using one or more I/O commands which transfer the data records in the sort-work output area to the external storage device. An I/O command may transfer one or more sort-work output area buffers (each buffer being a contiguous area of computer memory containing several data records) to the external storage device.
Step 7 repeats steps 2 through 6 until all the data records from the input file have been read, sorted, and written to the external storage device as ordered strings. This completes the first stage of the process.
At this point, the second stage in the process, called merging, begins. In this stage, the sorted strings stored in the external storage device are read into computer memory and the data records from each string are interleaved based on the value of their sort keys, producing the final, fully sorted output file.
The prior art merging stage starts with step 8, which is a different initialization than used during the first stage. The purpose of this step is to establish two sections of computer memory. The first section is the merge input area ("MIA"), which will receive the records read from the strings in the external storage device. The second section of computer memory established is the data output area which will contain the final sorted records after they have been moved from the merge input area. Any section of the data output area will consist of one or more data output area buffers, which act in the same manner as the sort-work output area buffers. As with the memory areas allocated in the first stage, these memory areas can be one large contiguous section of computer memory or several smaller areas.
Step 9 reads some of the data records from each of the strings stored in the external storage device into the merge input area. One or more I/O operations will be issued to the external storage device to read a portion of the records from each string. The number of data records to be read is based upon the size of the merge input area and the number of strings. An approximately equal number of data records from each string is read into the merge input area.
In step 10, the data records from the strings are merged and the resulting ordered records are moved to the data output area. Conceptually the merge process compares the value of the sort key from the next record from each string to find the record with the smallest key (assuming that the records are to be sorted in increasing value of the key). This data record is the "winner" and is then moved into the data output area.
Step 11 writes the sorted records from the data output area to the output file. One or more I/O commands will be used to transfer the data records from the data output area buffers to the output file. Each I/O command may transfer the data records from one or more buffers. Each data output area buffer is a contiguous area of computer memory containing one or more records.
Step 12 repeats steps 10 and 11 until all the data records from any particular string have been exhausted from the merge input area.
Step 13 repeats steps 9 through 12 until all the data records have been processed. In this manner, the merge input area is refreshed with further data records. With the completion of this step the final output of sorted data records are stored in the output file.
In cases of extremely great numbers of data records it may be necessary to perform the merge stage more than once. In such cases, after the intermediate merge, the output files are again merged.
The above process is described as a series of sequential steps for ease of description only. For efficiency, sort implementations try to obtain as much concurrency in these steps as possible. An example of this would be to read data records into the data input area concurrently with writing strings to the external storage device.